package everydayone.maxqueue;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Date 2020/03/07
 * @author 王光浩
 * @Thinking 使用两个队列来实现，一个普通队列，另一个是双端队列，前者按正常顺序来存储存入的值，后者维持一个
 * 			 单调递减队列，用于获取maxValue
 * 			 @ 在该题中核心问题是如何在O（1）时间复杂度内找到maxValue，这里的解决该问题的核心思路是：
  			      当向队列中插入一个元素时，只有前面比它大的元素会影响到maxValue，所有比插入元素小的元素都不不会影响到maxValue
 * @Analysis 平均复杂度为O（1），空间复杂为（n）
 */
public class MaxQueueTwo {
	LinkedList<Integer> queue;
	Deque<Integer> deque;
    public MaxQueueTwo() {
    	queue=new LinkedList<Integer>();  //普通队列
    	deque=new LinkedList<Integer>();//维持一个单调递减的队列
    }
    
    public int max_value() {
    	if(queue.isEmpty())
    		return -1;
    	return deque.getFirst();
    }
    public void push_back(int value) {
    	queue.add(value);
    	while(!deque.isEmpty() && deque.getLast()<value) //移除队列中所有比value小的元素
    		deque.pollLast();
    	deque.offerLast(value);
    }
    
    public int pop_front() {
    	if(queue.isEmpty())
    		return -1;
    	int re=queue.poll();
    	if(re==deque.getFirst())
    		deque.pollFirst();
    	return re;
    }
}
